package com.github.hgkmail.hello.leetcode101.pointer.graph.topologicalsort;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

import java.util.*;

//拓扑排序：BFS，队列里存放入度为0的顶点，这些点即是已排序，又影响邻接点的入度
//当找不到入度为0的顶点时，如果存在剩余的点入度大于0则原图有回路，如果剩余的点入度都是0则排序完成。
public class LC210CourseSchedule2 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses<=0) {
            return new int[]{};
        }
        //构建图和顶点的入度，从题意构建图使用List<List<Integer>>
        List<List<Integer>> graph = new ArrayList<>(numCourses);
        //初始化graph
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses];
        //初始化入度
        Arrays.fill(inDegree, 0);
        //根据题意构建边和入度
        for (int[] prerequisite : prerequisites) {
            //由于原来是[a,b]，a依赖b，这里要倒转一下: b->a
            int startVert=prerequisite[1];
            int endVert=prerequisite[0];
            graph.get(startVert).add(endVert);
            inDegree[endVert]+=1;
        }
        CommonUtil.printEdge(graph);

        //bfs，队列里面都是[入度为0的顶点]，这些顶点即是已知排序的点，又是影响入度的点
        Queue<Integer> queue=new ArrayDeque<>(numCourses);
        //晚点再转成数组
        List<Integer> res=new ArrayList<>();
        //把入度为0的点入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i]==0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int u = queue.poll();
            res.add(u);
            //更新邻接点的入度
            for (Integer v:graph.get(u)) {
                inDegree[v]--;
                if (inDegree[v]==0) {
                    queue.offer(v);
                }
            }
        }
        //检查是否有剩余的点，如果有则图有回路，无法拓扑排序
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i]>0) {
                return new int[]{};
            }
        }
        //转成数组
        int[] resArr=new int[res.size()];
        for (int i = 0; i < resArr.length; i++) {
            resArr[i]=res.get(i);
        }

        return resArr;
    }

    public static void main(String[] args) {
        int[] res=new LC210CourseSchedule2().findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}});
        System.out.println(Arrays.toString(res));
    }
}
